package test.algorithm;

import org.junit.Test;

/**
 * 八皇后游戏
 * 
 * @author 延晓磊
 *
 * @since 2020年7月3日
 */
public class QueenGame {
	
	// 摆法计数
	public static int count = 0;
	// 摆法：索引 = 行，值 = 列
	public static int[] arr = new int[8];
	
	@Test
	public void test() {
		put(0);
	}
	
	/**
	 * 推测摆法
	 * 
	 * @param n 皇后（行）
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月3日
	 */
	public static void put(int n) {
		// 递归出口：第8个皇后摆放完毕
		if (n == 8) {
			print();
			return;
		}
		// 从第1列开始，依次摆放皇后
		for (int i = 0; i < 8; i++) {
			// 摆放皇后
			arr[n] = i;
			// 校验冲突
			if (check(n)) {
				// 摆放下一个皇后
				put(n + 1);
			}
			// 依次尝试下一列
		}
	}
	
	/**
	 * 校验冲突
	 * 
	 * @param n
	 * @return
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月3日
	 */
	private static boolean check(int n) {
		// 校验当前皇后，与之前的皇后是否在同一条线
		for (int i = 0; i < n; i++) {
			// 索引i/n = 行，位置arr[i/n] = 列
			if (arr[i] == arr[n] || Math.abs(i-n) == Math.abs(arr[i]-arr[n]) ) {
				return false;
			}
		}
		return true;
	}
	
	/**
	 * 打印摆法
	 * 
	 * @author 延晓磊
	 *
	 * @since 2020年7月3日
	 */
	private static void print() {
		StringBuilder str = new StringBuilder();
		for (int i : arr) {
			str.append(i).append(" ");
		}
		System.out.println("第 " + ++count + " 种摆法：" + str);
	}
}
